package com.rui.study.algorithm.SORT_4_归并排序_分治思想_合并函数;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2018-11-08 15:06
 **/
public class MergeSort {

    /**
     * 归并排序：将两个数组分为前后两个部分，分别对两个部分排序，然后在合并两个有序的数组，最后拷贝回原数组，一直分解下去直到只有一个元素。
     * 最好时间复杂度：O(nlogn)
     * 最坏时间复杂度：O(nlogn)
     * 空间复杂度：O(n)，需要临时的空间来进行合并操作
     * 稳定性：稳定
     * @param a
     */
    public static void sort(int[] a) {
        int start = 0;
        int end = a.length - 1;
        int[] tmp = new int[a.length];
        recurse(a, start, end, tmp);
    }

    private static void recurse(int[] a, int start, int end, int[] tmp) {
        if (end > start) {
            // 分解
            int lend = start + (end - start) / 2;
            recurse(a, start, lend, tmp);
            recurse(a, lend + 1, end, tmp);

            // 合并
            int lidx = start;
            int ridx = lend + 1;
            for (int i=0; i<=end-start; i++) {
                tmp[i] = lidx > lend ? a[ridx++] : ridx > end ? a[lidx++] : a[lidx] <= a[ridx] ? a[lidx++] : a[ridx++];
            }

            // 拷回去
            for (int i=0; i<=end-start; i++) {
                a[start + i] = tmp[i];
            }
        }
    }
}
